package com.base.dp;

public class MaxPathSum {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) {
        // 构建测试用的二叉树
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(2);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(1);
        root.right.right = new TreeNode(-25);
        root.right.right.left = new TreeNode(3);
        root.right.right.right = new TreeNode(4);


        MaxPathSum maxPathSum = new MaxPathSum();
        System.out.println(maxPathSum.maxPathSum(root));
    }

    /**
     * 当前节点自身作为路径的一部分。
     * 当前节点加上左子树中的最大路径和。
     * 当前节点加上右子树中的最大路径和。
     * 当前节点加上左子树和右子树中的最大路径和（这是当前节点作为路径中的“分叉点”的情况）。
     * 对于每个节点，我们可以定义一个递归函数，该函数返回以当前节点为根的子树中，包含当前节点的最大路径和。在这个过程中，我们可以更新一个全局变量，以记录遍历过程中遇到的最大路径和。
     *
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0; //退出条件
        }
        //左边贡献值,只要正整数
        int left = Math.max(maxGain(node.left), 0);
        //右边贡献值
        int right = Math.max(maxGain(node.right), 0);

        //最大路径和
        int newSum = node.val + left + right;
        maxSum = Math.max(newSum, maxSum);
        //贡献值:是指以某个节点为根的子树能够贡献给其父节点的最大路径和。对于一个节点来说，它的最大贡献值取决于以下两个方面：
        //它自身的值（node.val）。
        //它左右子节点能提供的最大贡献值。但是，这里需要注意的是，一个节点只能选择其左右子节点中的一个来贡献给父节点，因为路径不能分叉。
        return node.val + Math.max(left, right);
    }
}
